# 目的： 用于管理内存使用的程序--按需分配和释放内存
#
# 注意： 使用这些例程的程序将要求一定大小的内存。在
#   实际操作中，我们使用的内存更大，但在回传指针前
#   将之放在开始处。我们增加一个大小字段，以及一个
#   AVAILABLE/UNAVAILABLE标记。因此，内存看起来
#   如下所示
#
# #########################################
# | AVAILABLE标记 | 内存大小 | 内存实际位置 |
# #########################################
#                                       ^返回指针指向此处
# 为了方便调用程序，返回的指针仅仅指向所请求的实际
# 内存位置，这也让我们无需更改调用程序即可更改结构

.section .data
# ###### 全局变量 ###### #
heap_begin:                 # 此处指向我们管理的内存的起始处
    .quad 0

current_break:              # 此处指向我们管理的内存之后的一个内存位置
    .quad 0

# #### 结构信息 ####
.equ HEADER_SIZE, 16        # 内存区头空间大小
.equ HDR_AVAIL_OFFSET, 0    # 头中AVAILABLE标志的位置
.equ HDR_SIZE_OFFSET, 8     # 内存区中大小字段的位置

# #### 常量 #####
.equ UNAVAILABLE, 0         # 这是用于标记已分配空间的数字
.equ AVAILABLE, 1           # 这是用于标记已回收空间的数字，此类空间可用于再分配
.equ SYS_BRK, 45            # 用于中断系统调用的系统调用好
.equ LINUX_SYSCALL, 0x80    # 使系统调用号更易读

.section .text
# #### 函数 ####
# # allocate_init # #
# 目的：调用此函数来初始化函数（更具体的说，此函数设置
# heap_begin和current_break）。此函数无参数和返回值
.globl allocate_init
.type allocate_init, @function
allocate_init:
    push    %rbp                # 标准函数处理
    mov     %rsp, %rbp

    # 如果发起brk系统调用，%ebx内容为0， 该调用将返回最后一个有效可用地址
    mov     $SYS_BRK, %rax      # 确定中断点
    mov     $0, %rbx
    int     $LINUX_SYSCALL

    inc     %rax                # %eax现为最后有效可用地址，
                                # 我们需要此地址之后的内存位置
    movl     %eax, current_break # 保存当前中断
    movl     %eax, heap_begin    # 将当前中断保存为我们的首地址，这会使分配
                                # 函数在其首次运行时从linux获取更多的内存
    mov     %rbp, %rsp
    pop     %rbp
    ret

# # 函数结束 # #

# # allocate # #
# 目的：此函数用于获取一段内存。它查看是否存在自由内存块
#      如不存在，则向linux请求
#
# 参数：此函数有一个参数，就是我们要求的内存块大小
#
# 返回值：此函数将所分配内存的地址返回到%eax中。如果已无内存可用，
#       就返回0.
#
# #### 处理 #### #
# 用到的变量：
#
# %ecx - 保存所请求内存的大小（这是第一个也是唯一的参数）
# %eax - 检测的当前内存区
# %ebx - 当前中断位置
# %edx - 当前内存大小
#
# 我们检测每个以heap_begin开始的内存区，查看每一个的大小以及是否已经分配
# 如果某个内存区大于等于所请求的大小，且可用，该函数就获取此内存区
# 如果无法找到足够大的内存区，就像linux请求更多内存，这种情况下，此函数
# 会向前移动current_break
.globl allocate
.type allocate, @function
.equ ST_MEM_SIZE, 16        # 用于分配内存大小的栈位置
allocate:
    push    %rbp
    mov     %rsp, %rbp

    mov     ST_MEM_SIZE(%rbp), %rcx # 保存所请求内存的大小

    mov     heap_begin, %rax        # 保存当前搜索位置
    mov     current_break, %rbx     # 保存当前中断

alloc_loop_begin:                   # 循环搜索每个内存区
    cmp     %rbx, %rax              # 如果两者相等，就表明需要更多的内存
    je      move_break

    # 获得此内存区的大小
    mov     HDR_SIZE_OFFSET(%rbp), %rdx
    # 如果无空间可用， 则继续搜索下一块内存区
    cmp     $UNAVAILABLE, HDR_AVAIL_OFFSET(%rax)
    je      next_location

    cmp     %rdx, %rcx              # 如果内存区可用，就将之与所需大小进行比较
    jle     allocate_here           # 如果足够大，就跳转至allocate_here

next_location:
    add     $HEADER_SIZE, %rax      # 内存区总大小为所需大小（当前%edx中存储的值）
    add     %rdx, %rax              # + 内存头8字节

                                    # （标志4字节+内存区大小4字节） 
                                    # 因此将%edx与$8相加，结果存于%eax中，
                                    # 即可获取下一个可用内存区

    jmp     alloc_loop_begin        # 查看下一个位置

allocate_here:          # 如果执行此处代码，说明要分配的内存区头在%eax中
    # 将空间标识为不可用
    movq    $UNAVAILABLE, HDR_AVAIL_OFFSET(%rax)
    mov     $HEADER_SIZE, %rax      # 将可用内存区头的下一个位置移入%eax
                                    # （因为这是我们要返回的内容）
    mov     %rbp, %rsp
    pop     %rbp
    ret

move_break: # 如果执行到这里，说明已经耗尽所有可寻址内存，需要请求更多
            # 的内存， %ebx保存当前数据结束处位置，%ecx保存数据大小

    add     $HEADER_SIZE, %rbx      # 需要增加%ebx的值，使之为我们想要内存结束
    add     %rcx, %rbx              # 的地方，因此要将其与内存区域头结构的大小相加
                                    # 然后将中断与所请求数据的大小相加
                                    
                                    # 接着就要向linux要求更多内存

    push    %rax                    # 保存所需寄存器
    push    %rcx
    push    %rbx

    mov     $SYS_BRK, %rax          # 重置中断
    int     $LINUX_SYSCALL

    # 正常情况下，应返回新中断到%eax中，如果返回失败，返回值为0，
    # 否则新中断应大于等于我们请求的内存，在本程序中，我们并不关心
    # 实际中断设置在何处，
    # 只要%eax的内容不为0，我们并关心其实际值。

    cmp     $0, %rax                # 监测错误情况
    je      error

    pop     %rbx
    pop     %rcx
    pop     %rax

    # 设置该内存为不可用，因为我们将分配该内存
    movq    $UNAVAILABLE, HDR_AVAIL_OFFSET(%rax)
    # 设置该内存的大小
    mov     %rcx, HDR_SIZE_OFFSET(%rax)
    # 将%eax移至可用内存的实际起始处。%eax现保存着返回值
    add     $HEADER_SIZE, %rax

    mov     %rbx, current_break     # 保存新中断

    mov     %rbp, %rsp
    pop     %rbp
    ret

error:
    mov     $0, %rax                # 如果出错就返回0
    mov     %rbp, %rsp
    pop     %rbp
    ret
# #### 函数结束 #### #

# # deallocate # #
# 目的: 此函数的目的是使用内存区域后将之返回到内存池中
#
# 参数：唯一的参数是我们要返回到内存池的内存地址
#
# 返回值：无返回值
#
# 具体处理：你是否还记得，我们实际上将可用内存起始位置传递给程序，
#         该起始位置就是内存区起始处加上0个存储位置，我们只需要
#         倒退8个存储位置，然后标记此内存区为可用即可，这样分配
#         函数就直到可以使用此内存区了
.globl deallocate
.type deallocate,@function
.equ ST_MEMORY_SEG, 8
deallocate:
    # 因为此函数很简单，我们无需再用专门函数获取要释放的内存地址
    # （通常该内存地址为8(%ebp)），但由于我们并未将%ebp入栈或将
    # %esp内容移至%ebp，此处使用4(%esp)
    mov     ST_MEMORY_SEG(%rsp), %rax

    # 获得指向内存实际起始处的指针
    sub     $HEADER_SIZE, %rax
    # 标识该内存区为可用
    movq    $AVAILABLE, HDR_AVAIL_OFFSET(%rax)

    ret
# #### 函数结束 #### #
